Multiprotocol Label Switching (MPLS) is a networking protocol in which network nodes forward packets based upon labels. MPLS can integrate Layer 2 and Layer 3 routing and, as such, this protocol can form the bridge from connectionless IP (Internet Protocol) networks to connection-oriented networks, such as ATM (Asynchronous Transfer Mode) networks, frame relay networks, and optical networks (e.g., a Synchronous Optical Network, or SONET). By forming a bridge between IP and Layer 2 technologies such as ATM, MPLS enables the creation of hybrid IP and ATM (or frame relay) networks. Thus, MPLS makes available to the network layer (e.g., the IP layer) many capabilities (e.g., Quality of Service, or QoS, and traffic management) that traditionally existed at Layer 2.
The MPLS protocol is defined by a family of specifications promulgated by the Internet Engineering Task Force (IETF) and available at “http://www.ietf.org/”. Specifications defining the MPLS protocol include, for example, IETF Request for Comments (RFC) 3031, Multiprotocol Label Switching Architecture (2001), and IETF RFC 2702, Requirements for Traffic Engineering Over MPLS (1999). It should be understood, however, that the above-listed documents are but a few examples of specifications relating to MPLS and, further, that other aspects of MPLS may be described in other specifications.
MPLS provides the ability to build virtual circuits across a network using one or more of the aforementioned labels. A virtual circuit through an MPLS network comprises a series of nodes, including an ingress node, one or more intermediate nodes, and an egress node. The nodes at the edges of the MPLS network—i.e., the ingress and egress nodes—are referred to as Label Edge Routers (or LERs), whereas the intermediate nodes are referred to as Label Switching Routers (or LSRs). The LERs couple the MPLS network with other, external networks, whereas the LSRs form the core of the MPLS network.
An MPLS label comprises an identifier (e.g., a number of bits) that represents a packet's Forwarding Equivalence Class (FEC), which is a group of packets that are forwarded in the same manner (e.g., over the same network path). The MPLS label in a packet can serve as an index into a forwarding table which specifies the next node, or next hop, for the packet. The path associated with a virtual circuit within an MPLS network—this virtual circuit path referred to as a Label Switched Path (or LSP)—is delineated by one or more MPLS labels that are, at various times, encapsulated into packets propagating over this path. Because of the ability to create LSRs through an MPLS network, MPLS supports priority-based routing—e.g., QoS and/or Class of Service (CoS)—as well as traffic engineering schemes.
As noted above, the path of a packet through an MPLS network is defined by MPLS labels. These labels include the information needed to determine a packet's route through the network and, other than examining a label to determine the next hop for a packet, the nodes within the MPLS network (e.g., the LSRs) do not have to make routing decisions. A packet arriving at an ingress LER of an MPLS network will receive a label indicating the packet's first hop in the network. When the packet is received at an LSR within the core of the MPLS network, the LSR may simply remove (or “POP”) the label from the packet and then replace (or “SWAP”) that label with another label. As the packet travels through the MPLS network, that packet may, at any time, have multiple labels (i.e., a “label stack”) that have been encapsulated within the packet. When the packet reaches the edge of the MPLS network, the egress LER will POP all labels from the label stack in order to make a forwarding decision for the packet.
Each node in an MPLS network maintains a forwarding table including an Incoming Label Mapping (ILM) table and a Next Hop Label Forwarding Entries (NHLFE) table. The ILM table at a given node maps each incoming label at that node to an associated action and, perhaps, to an entry in the NHLFE table, which will specify the next-hop for an incoming packet. For example, when a packet is received at an MPLS network node, a look-up is performed in that node's ILM table based upon the label of the incoming packet, and the entry of the ILM table corresponding to the incoming label may specify an action, such as SWAP, and this ILM table entry will map to an entry in the NHLFE table. The entry of the NHLFE table will then specify a new label that is to replace the incoming label, and this NHLFE table entry may also specify an outgoing port.
At each egress LER of an MPLS domain, there will not be an NHLFE table, as there is no next-hop within the MPLS domain for any packet arriving at an egress node. Thus, at any egress LER, a look-up in that LER's associated ILM table can inform the egress LER how to forward or otherwise dispose of a labeled packet. As previously suggested, a packet received at the egress LER may contain a label stack, rather than a single label. Should a label stack be encapsulated in a received packet, the egress LER may need to “look” at each label in the stack one-by-one in order to determine what action to take with respect to the packet.
The ILM table associated with an egress LER is usually stored in an external (e.g., off-chip) memory, as many processing devices do not include sufficient on-chip memory to hold the entire ILM table. Thus, should the egress LER receive a packet including multiple labels, the LER may need to POP each label from the stack one-by-one. However, because the ILM table is located in off-chip memory, the look-up based on each label will require a separate access to external memory. For a packet including a large label stack, the number of external memory accesses needed to process the label stack can be very time consuming. For applications requiring a high throughput, these external memory accesses can adversely affect performance of the MPLS network.